home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / TPLY30.ARJ / TPLY.DOC < prev    next >
Text File  |  1991-06-17  |  58KB  |  1,512 lines

  1.  
  2.  
  3.       TP Lex and Yacc - The Compiler Writer's Tools for Turbo Pascal
  4.       == === === ==== = === ======== ======== ===== === ===== ======
  5.  
  6.                      Version 3.0 User Manual
  7.                      ======= === ==== ======
  8.  
  9.                          Albert Graef
  10.                        Schillerstr. 18
  11.                        6509 Schornsheim
  12.  
  13.                ag@informatik.mathematik.uni-mainz.de
  14.  
  15.                         June 17, 1991
  16.  
  17.  
  18. Introduction
  19. ============
  20.  
  21. This document describes the TP Lex and Yacc compiler generator toolset.
  22. These tools are designed especially to help you prepare compilers and
  23. similar programs like text processing utilities and command language
  24. interpreters with the Turbo Pascal (TM) programming language.
  25.  
  26. TP Lex and Yacc are Turbo Pascal adaptions of the well-known UNIX (TM)
  27. utilities Lex and Yacc, which were written by M.E. Lesk and S.C. Johnson
  28. at Bell Laboratories, and are used with the C programming language. TP Lex
  29. and Yacc are intended to be approximately "compatible" with these programs.
  30. However, they are an independent development of the author, based on the
  31. techniques described in the famous "dragon book" of Aho, Sethi and Ullman
  32. (Aho, Sethi, Ullman: "Compilers : principles, techniques and tools," Reading
  33. (Mass.), Addison-Wesley, 1986).
  34.  
  35. TP Lex and Yacc, like any other tools of this kind, are not intended for
  36. novices or casual programmers; they require extensive programming experience
  37. as well as a thorough understanding of the principles of parser design and
  38. implementation to be put to work successfully. But if you are a seasoned
  39. Turbo Pascal programmer with some background in compiler design and formal
  40. language theory, you will almost certainly find TP Lex and Yacc to be a
  41. powerful extension of your Turbo Pascal toolset.
  42.  
  43. This manual tells you how to get started with the TP Lex and Yacc programs
  44. and provides a short description of these programs. Some knowledge about
  45. the C versions of Lex and Yacc will be useful, although not strictly
  46. necessary. For further reading, you may also refer to:
  47.  
  48. - Aho, Sethi and Ullman: "Compilers : principles, techniques and tools."
  49.   Reading (Mass.), Addison-Wesley, 1986.
  50.  
  51. - Johnson, S.C.: "Yacc - yet another compiler-compiler." CSTR-32, Bell
  52.   Telephone Laboratories, 1974.
  53.  
  54. - Lesk, M.E.: "Lex - a lexical analyser generator." CSTR-39, Bell Telephone
  55.   Laboratories, 1975.
  56.  
  57. - Schreiner, Friedman: "Introduction to compiler construction with UNIX."
  58.   Prentice-Hall, 1985.
  59.  
  60. - The Unix Programmer's Manual, Sections `Lex' and `Yacc'.
  61.  
  62.  
  63. Getting Started
  64. ---------------
  65.  
  66. The TP Lex and Yacc programs run on IBM PC compatible computers with MS-
  67. DOS 3.0 (or later) and Turbo Pascal compiler (Version 4.0 or later). Your
  68. system should have at least 512 KB RAM; a hard disk is recommended, while
  69. not strictly necessary.
  70.  
  71. To install TP Lex and Yacc on your system, simply copy the files on the
  72. distribution disk to an appropriate directory on your hard disk. Then
  73. put this directory on your DOS PATH and Turbo Pascal's unit search path
  74. (such that the Turbo Pascal compiler finds the TP Lex and Yacc library
  75. units).
  76.  
  77. The library units (.TPU files) in the distribution are compiled with
  78. Turbo Pascal 6.0. If you are using a different Turbo Pascal version,
  79. you will have to recompile these units (sources are provided in the
  80. corresponding LEXLIB.PAS and YACCLIB.PAS files).
  81.  
  82. Having installed TP Lex and Yacc on your system, you can now compile
  83. your first TP Lex and Yacc program EXPR. EXPR is a simple desktop
  84. calculator program which consists of a lexical analyzer in the TP Lex
  85. source file EXPRLEX.L and the parser and main program in the TP Yacc
  86. source file EXPR.Y. To compile these programs, issue the commands
  87.  
  88.    lex exprlex
  89.    yacc expr
  90.  
  91. That's it! You now have the Turbo Pascal sources (EXPRLEX.PAS and EXPR.PAS)
  92. for the EXPR program. Use the Turbo Pascal compiler to compile these
  93. programs as follows:
  94.  
  95.    tpc expr
  96.  
  97. You can now execute the EXPR program and type some expressions to see it
  98. work (terminate the program with an empty line). There is a number of other
  99. sample TP Lex and Yacc programs (.L and .Y files) on the distribution
  100. disk, including a TP Yacc cross reference utility and a complete parser
  101. for Standard Pascal.
  102.  
  103. The TP Lex and Yacc programs recognize some options which may be specified
  104. anywhere on the command line. E.g.,
  105.  
  106.    lex /o exprlex
  107.  
  108. runs TP Lex with "DFA optimization" and
  109.  
  110.    yacc /v expr
  111.  
  112. runs TP Yacc in "verbose" mode (TP Yacc generates a readable description
  113. of the generated parser).
  114.  
  115. The TP Lex and Yacc programs use the following default filename extensions:
  116. - .L:   TP Lex input files
  117. - .Y:   TP Yacc input files
  118. - .PAS: TP Lex and Yacc output files
  119.  
  120. As usual, you may overwrite default filename extensions by explicitly
  121. specifying suffixes.
  122.  
  123. If you ever forget how to run TP Lex and Yacc, you can issue the command
  124.  
  125.    lex
  126.  
  127. or
  128.  
  129.    yacc
  130.  
  131. without arguments to get a short summary of the command line syntax.
  132.  
  133.  
  134.  
  135. TP Lex
  136. ======
  137.  
  138. This section describes the TP Lex lexical analyzer generator.
  139.  
  140.  
  141. Usage
  142. -----
  143.  
  144. LEX [options] lex-file[.L] [output-file[.PAS]]
  145.  
  146.  
  147. Options
  148. -------
  149.  
  150. /v  "Verbose:" Lex generates a readable description of the generated
  151.     lexical analyzer, written to lex-file with new extension .LST.
  152.  
  153. /o  "Optimize:" Lex optimizes DFA tables to produce a minimal DFA.
  154.  
  155.  
  156. Description
  157. -----------
  158.  
  159. TP Lex is a program generator that is used to generate the Turbo Pascal
  160. source code for a lexical analyzer subroutine from the specification
  161. of an input language by a regular expression grammar.
  162.  
  163. TP Lex parses the source grammar contained in lex-file (with default
  164. suffix .L) and writes the constructed lexical analyzer subroutine
  165. to the specified output-file (with default suffix .PAS); if no output
  166. file is specified, output goes to lex-file with new suffix .PAS.
  167. If any errors are found during compilation, error messages are written
  168. to the list file (lex-file with new suffix .LST).
  169.  
  170. The generated output file contains a lexical analyzer routine, yylex,
  171. implemented as:
  172.  
  173.   function yylex : Integer;
  174.  
  175. This routine has to be called by your main program to execute the lexical
  176. analyzer. The return value of the yylex routine usually denotes the number
  177. of a token recognized by the lexical analyzer (see the return routine
  178. in the LexLib unit). At end-of-file the yylex routine normally returns 0.
  179.  
  180. The code template for the yylex routine may be found in the YYLEX.COD
  181. file. This file is needed by TP Lex when it constructs the output file.
  182. It must be present either in the current directory or in the directory
  183. from which TP Lex was executed (TP Lex searches these directories in
  184. the indicated order).
  185.  
  186. The TP Lex library (LexLib) unit is required by programs using Lex-generated
  187. lexical analyzers; you will therefore have to put an appropriate uses clause
  188. into your program or unit that contains the lexical analyzer routine. The
  189. LexLib unit also provides various useful utility routines; see the file
  190. LEXLIB.PAS for further information.
  191.  
  192.  
  193. Lex Source
  194. ----------
  195.  
  196. A TP Lex program consists of three sections separated with the %% delimiter:
  197.  
  198. definitions
  199. %%
  200. rules
  201. %%
  202. auxiliary procedures
  203.  
  204. All sections may be empty. The TP Lex language is line-oriented; definitions
  205. and rules are separated by line breaks. There is no special notation for
  206. comments, but (Turbo Pascal style) comments may be included as Turbo Pascal
  207. fragments (see below).
  208.  
  209. The definitions section may contain the following elements:
  210.  
  211. - regular definitions in the format:
  212.  
  213.      name   substitution
  214.  
  215.   which serve to abbreviate common subexpressions. The {name} notation
  216.   causes the corresponding substitution from the definitions section to
  217.   be inserted into a regular expression. The name must be a legal
  218.   identifier (letter followed by a sequence of letters and digits;
  219.   the underscore counts as a letter; upper- and lowercase are distinct).
  220.   Regular definitions must be non-recursive.
  221.  
  222. - start state definitions in the format:
  223.  
  224.      %start name ...
  225.  
  226.   which are used in specifying start conditions on rules (described
  227.   below). The %start keyword may also be abbreviated as %s or %S.
  228.  
  229. - Turbo Pascal declarations enclosed between %{ and %}. These will be
  230.   inserted into the output file (at global scope). Also, any line that
  231.   does not look like a Lex definition (e.g., starts with blank or tab)
  232.   will be treated as Turbo Pascal code. (In particular, this also allows
  233.   you to include Turbo Pascal comments in your Lex program.)
  234.  
  235. The rules section of a TP Lex program contains the actual specification of
  236. the lexical analyzer routine. It may be thought of as a big CASE statement
  237. discriminating over the different patterns to be matched and listing the
  238. corresponding statements (actions) to be executed. Each rule consists of a
  239. regular expression describing the strings to be matched in the input, and a
  240. corresponding action, a Turbo Pascal statement to be executed when the
  241. expression matches. Expression and statement are delimited with whitespace
  242. (blanks and/or tabs). Thus the format of a Lex grammar rule is:
  243.  
  244.    expression      statement;
  245.  
  246. Note that the action must be a single Turbo Pascal statement terminated
  247. with a semicolon (use begin ... end for compound statements). The statement
  248. may span multiple lines if the successor lines are indented with at least
  249. one blank or tab. The action may also be replaced by the | character,
  250. indicating that the action for this rule is the same as that for the next
  251. one.
  252.  
  253. The TP Lex library unit provides various variables and routines which are
  254. useful in the programming of actions. In particular, the yytext string
  255. variable holds the text of the matched string, and the yyleng Byte variable
  256. its length.
  257.  
  258. Regular expressions are used to describe the strings to be matched in a
  259. grammar rule. They are built from the usual constructs describing character
  260. classes and sequences, and operators specifying repetitions and alternatives.
  261. The precise format of regular expressions is described in the next section.
  262.  
  263. The rules section may also start with some Turbo Pascal declarations
  264. (enclosed in %{ %}) which are treated as local declarations of the
  265. actions routine.
  266.  
  267. Finally, the auxiliary procedures section may contain arbitrary Turbo
  268. Pascal code (such as supporting routines or a main program) which is
  269. simply tacked on to the end of the output file. The auxiliary procedures
  270. section is optional.
  271.  
  272.  
  273. Regular Expressions
  274. -------------------
  275.  
  276. The following table summarizes the format of the regular expressions
  277. recognized by TP Lex (also compare Aho, Sethi, Ullman 1986, fig. 3.48).
  278. c stands for a single character, s for a string, r for a regular expression,
  279. and n,m for nonnegative integers.
  280.  
  281. expression   matches                        example
  282. ----------   ----------------------------   -------
  283. c            any non-operator character c   a
  284. \c           character c literally          \*
  285. "s"          string s literally             "**"
  286. .            any character but newline      a.*b
  287. ^            beginning of line              ^abc
  288. $            end of line                    abc$
  289. [s]          any character in s             [abc]
  290. [^s]         any character not in s         [^abc]
  291. r*           zero or more r's               a*
  292. r+           one or more r's                a+
  293. r?           zero or one r                  a?
  294. r{m,n}       m to n occurrences of r        a{1,5}
  295. r{m}         m occurrences of r             a{5}
  296. r1r2         r1 then r2                     ab
  297. r1|r2        r1 or r2                       a|b
  298. (r)          r                              (a|b)
  299. r1/r2        r1 when followed by r2         a/b
  300. <x>r         r when in start condition x    <x>abc
  301. ---------------------------------------------------
  302.  
  303. The operators *, +, ? and {} have highest precedence, followed by
  304. concatenation. The | operator has lowest precedence. Parentheses ()
  305. may be used to group expressions and overwrite default precedences.
  306. The <> and / operators may only occur once in an expression.
  307.  
  308. The usual C-like escapes are recognized:
  309.  
  310. \n     denotes newline
  311. \r     denotes carriage return
  312. \t     denotes tab
  313. \b     denotes backspace
  314. \f     denotes form feed
  315. \NNN   denotes character no. NNN in octal base
  316.  
  317. You can also use the \ character to quote characters which would otherwise
  318. be interpreted as operator symbols. In character classes, you may use
  319. the - character to denote ranges of characters. For instance, [a-z]
  320. denotes the class of all lowercase letters.
  321.  
  322. The expressions in a TP Lex program may be ambigious, i.e. there may be inputs
  323. which match more than one rule. In such a case, the lexical analyzer prefers
  324. the longest match and, if it still has the choice between different rules,
  325. it picks the first of these. If no rule matches, the lexical analyzer
  326. executes a default action which consists of copying the input character
  327. to the output unchanged. Thus, if the purpose of a lexical analyzer is
  328. to translate some parts of the input, and leave the rest unchanged, you
  329. only have to specify the patterns which have to be treated specially. If,
  330. however, the lexical analyzer has to absorb its whole input, you will have
  331. to provide rules that match everything. E.g., you might use the rules
  332.  
  333.    .   |
  334.    \n  ;
  335.  
  336. which match "any other character" (and ignore it).
  337.  
  338. Sometimes certain patterns have to be analyzed differently depending on some
  339. amount of context in which the pattern appears. In such a case the / operator
  340. is useful. For instance, the expression a/b matches a, but only if followed
  341. by b. Note that the b does not belong to the match; rather, the lexical
  342. analyzer, when matching an a, will look ahead in the input to see whether
  343. it is followed by a b, before it declares that it has matched an a. Such
  344. lookahead may be arbitrarily complex (up to the size of the LexLib input
  345. buffer). E.g., the pattern a/.*b matches an a which is followed by a b
  346. somewhere on the same input line. TP Lex also has a means to specify left
  347. context which is described in the next section.
  348.  
  349.  
  350. Start Conditions
  351. ----------------
  352.  
  353. TP Lex provides some features which make it possible to handle left context.
  354. The ^ character at the beginning of a regular expression may be used to
  355. denote the beginning of the line. More distant left context can be described
  356. conveniently by using start conditions on rules.
  357.  
  358. Any rule which is prefixed with the <> construct is only valid if the lexical
  359. analyzer is in the denoted start state. For instance, the expression <x>a
  360. can only be matched if the lexical analyzer is in start state x. You can have
  361. multiple start states in a rule; e.g., <x,y>a can be matched in start states
  362. x or y.
  363.  
  364. Start states have to be declared in the definitions section by means of
  365. one or more start state definitions (see above). The lexical analyzer enters
  366. a start state through a call to the LexLib routine start. E.g., you may
  367. write:
  368.  
  369. %start x y
  370. %%
  371. <x>a    start(y);
  372. <y>b    start(x);
  373. %%
  374. begin
  375.   start(x); if yylex=0 then ;
  376. end.
  377.  
  378. Upon initialization, the lexical analyzer is put into state x. It then
  379. proceeds in state x until it matches an a which puts it into state y.
  380. In state y it may match a b which puts it into state x again, etc.
  381.  
  382. Start conditions are useful when certain constructs have to be analyzed
  383. differently depending on some left context (such as a special character
  384. at the beginning of the line), and if multiple lexical analyzers have to
  385. work in concert. If a rule is not prefixed with a start condition, it is
  386. valid in all user-defined start states, as well as in the lexical analyzer's
  387. default start state.
  388.  
  389.  
  390. Lex Library
  391. -----------
  392.  
  393. The TP Lex library (LexLib) unit provides various variables and routines
  394. which are used by Lex-generated lexical analyzers and application programs.
  395. It provides the input and output streams and other internal data structures
  396. used by the lexical analyzer routine, and supplies some variables and utility
  397. routines which may be used by actions and application programs. Refer to
  398. the file LEXLIB.PAS for a closer description.
  399.  
  400. You can also modify the Lex library unit (and/or the code template in the
  401. YYLEX.COD file) to customize TP Lex to your target applications. E.g.,
  402. you might wish to optimize the code of the lexical analyzer for some
  403. special application, make the analyzer read from/write to memory instead
  404. of files, etc.
  405.  
  406.  
  407. Implementation Restrictions And Bugs
  408. ------------------------------------
  409.  
  410. Internal table sizes and the main memory available limit the complexity
  411. of source grammars that TP Lex can handle. There is currently no possibility
  412. to change internal table sizes (apart from modifying the sources of TP Lex
  413. itself), but the maximum table sizes provided by TP Lex seem to be large
  414. enough to handle most realistic applications. The current limits are
  415. 600 p (positions), 300 s (states) and 600 t (transitions).
  416.  
  417. As implemented, the generated DFA table is stored as a typed array constant
  418. which is inserted into the YYLEX.COD code template. The transitions in each
  419. state are stored in order. Of course it would have been more efficient to
  420. generate a big CASE statement instead, but I found that this may cause
  421. problems with the encoding of large DFA tables because Turbo Pascal has
  422. a quite rigid limit on the code size of individual procedures. I decided to
  423. use a scheme in which transitions on different symbols to the same state are
  424. merged into one single transition (specifying a character set and the
  425. corresponding next state). This keeps the number of transitions in each state
  426. quite small and still allows a fairly efficient access to the transition
  427. table.
  428.  
  429. The TP Lex program has an option (/o) to optimize DFA tables. This causes
  430. a minimal DFA to be generated, using the algorithm described in Aho, Sethi,
  431. Ullman (1986). Although the absolute limit on the number of DFA states that
  432. TP Lex can handle is 300, TP Lex poses an additional restriction (100) on
  433. the number of states in the initial partition of the DFA optimization
  434. algorithm. Thus, you may get a fatal `integer set overflow' message when
  435. using the /o option even when TP Lex is able to generate an unoptimized DFA.
  436. In such cases you will just have to be content with the unoptimized DFA.
  437. (Anyhow, using the merged transitions scheme described above, TP Lex usually
  438. constructs unoptimized DFA's which are not far from being optimal, and thus
  439. in most cases DFA optimization won't have a great impact on DFA table sizes.)
  440.  
  441.  
  442. Differences from UNIX Lex
  443. -------------------------
  444.  
  445. Major differences between TP Lex and UNIX Lex are listed below.
  446.  
  447. - TP Lex produces output code for Turbo Pascal, rather than for C.
  448.  
  449. - Character tables (%T) are not supported; neither are any directives
  450.   to determine internal table sizes (%p, %n, etc.).
  451.  
  452. - Library routines are named differently from the UNIX version (e.g.,
  453.   the `start' routine takes the place of the `BEGIN' macro of UNIX
  454.   Lex), and, of course, all macros of UNIX Lex (ECHO, REJECT, etc.) had
  455.   to be implemented as procedures.
  456.  
  457.  
  458.  
  459. TP Yacc
  460. =======
  461.  
  462. This section describes the TP Yacc compiler compiler.
  463.  
  464.  
  465. Usage
  466. -----
  467.  
  468. YACC [options] yacc-file[.Y] [output-file[.PAS]]
  469.  
  470.  
  471. Options
  472. -------
  473.  
  474. /v  "Verbose:" TP Yacc generates a readable description of the generated
  475.     parser, written to yacc-file with new extension .LST.
  476.  
  477. /d  "Debug:" TP Yacc generates parser with debugging output.
  478.  
  479.  
  480. Description
  481. -----------
  482.  
  483. TP Yacc is a program that lets you prepare parsers from the description
  484. of input languages by BNF-like grammars. You simply specify the grammar
  485. for your target language, augmented with the Turbo Pascal code necessary
  486. to process the syntactic constructs, and TP Yacc translates your grammar
  487. into the Turbo Pascal code for a corresponding parser subroutine named
  488. yyparse.
  489.  
  490. TP Yacc parses the source grammar contained in yacc-file (with default
  491. suffix .Y) and writes the constructed parser subroutine to the specified
  492. output-file (with default suffix .PAS); if no output file is specified,
  493. output goes to yacc-file with new suffix .PAS. If any errors are found
  494. during compilation, error messages are written to the list file (yacc-file
  495. with new suffix .LST).
  496.  
  497. The generated parser routine, yyparse, is declared as:
  498.  
  499.    function yyparse : Integer;
  500.  
  501. This routine may be called by your main program to execute the parser.
  502. The return value of the yyparse routine denotes success or failure of
  503. the parser (possible return values: 0 = success, 1 = unrecoverable syntax
  504. error or parse stack overflow).
  505.  
  506. The code template for the yyparse routine may be found in the YYPARSE.COD
  507. file. This file is needed by TP Yacc when it constructs the output file.
  508. It must be present either in the current directory or in the directory
  509. from which TP Yacc was executed (TP Yacc searches these directories in
  510. the indicated order).
  511.  
  512. The TP Yacc library (YaccLib) unit is required by programs using Yacc-
  513. generated parsers; you will therefore have to put an appropriate uses clause
  514. into your program or unit that contains the parser routine. The YaccLib unit
  515. also provides some routines which may be used to control the actions of the
  516. parser. See the file YACCLIB.PAS for further information.
  517.  
  518.  
  519. Yacc Source
  520. -----------
  521.  
  522. A TP Yacc program consists of three sections separated with the %% delimiter:
  523.  
  524. definitions
  525. %%
  526. rules
  527. %%
  528. auxiliary procedures
  529.  
  530.  
  531. The TP Yacc language is free-format: whitespace (blanks, tabs and newlines)
  532. is ignored, except if it serves as a delimiter. Comments have the C-like
  533. format /* ... */. They are treated as whitespace. Grammar symbols are denoted
  534. by identifiers which have the usual form (letter, including underscore,
  535. followed by a sequence of letters and digits; upper- and lowercase is
  536. distinct). The TP Yacc language also has some keywords which always start
  537. with the % character. Literals are denoted by characters enclosed in single
  538. quotes. The usual C-like escapes are recognized:
  539.  
  540. \n     denotes newline
  541. \r     denotes carriage return
  542. \t     denotes tab
  543. \b     denotes backspace
  544. \f     denotes form feed
  545. \NNN   denotes character no. NNN in octal base
  546.  
  547.  
  548. Definitions
  549. -----------
  550.  
  551. The first section of a TP Yacc grammar serves to define the symbols used in
  552. the grammar. It may contain the following types of definitions:
  553.  
  554. - start symbol definition: A definition of the form
  555.  
  556.      %start symbol
  557.  
  558.   declares the start nonterminal of the grammar (if this definition is
  559.   omitted, TP Yacc assumes the left-hand side nonterminal of the first
  560.   grammar rule as the start symbol of the grammar).
  561.  
  562. - terminal definitions: Definitions of the form
  563.  
  564.      %token symbol ...
  565.  
  566.   are used to declare the terminal symbols ("tokens") of the target
  567.   language. Any identifier not introduced in a %token definition will
  568.   be treated as a nonterminal symbol.
  569.  
  570.   As far as TP Yacc is concerned, tokens are atomic symbols which do not
  571.   have an innert structure. A lexical analyzer must be provided which
  572.   takes on the task of tokenizing the input stream and return the
  573.   individual tokens and literals to the parser (see Section `Lexical
  574.   Analysis').
  575.  
  576. - precedence definitions: Operator symbols (terminals) may be associated
  577.   with a precedence by means of a precedence definition which may have
  578.   one of the following forms
  579.  
  580.      %left symbol ...
  581.      %right symbol ...
  582.      %nonassoc symbol ...
  583.  
  584.   which are used to declare left-, right- and nonassociative operators,
  585.   respectively. Each precedence definition introduces a new precedence
  586.   level, lowest precedence first. E.g., you may write:
  587.  
  588.      %nonassoc '<' '>' '=' GEQ LEQ NEQ  /* relational operators */
  589.      %left     '+' '-'  OR              /* addition operators */
  590.      %left     '*' '/' AND              /* multiplication operators */
  591.      %right    NOT UMINUS               /* unary operators */
  592.  
  593.   A terminal identifier introduced in a precedence definition may, but
  594.   need not, appear in a %token definition as well.
  595.  
  596. - type definitions: Any (terminal or nonterminal) grammar symbol may be
  597.   associated with a type identifier which is used in the processing of
  598.   semantic values. Type tags of the form <name> may be used in token and
  599.   precedence definitions to declare the type of a terminal symbol, e.g.:
  600.  
  601.      %token <Real>  NUM
  602.      %left  <AddOp> '+' '-'
  603.  
  604.   To declare the type of a nonterminal symbol, use a type definition of
  605.   the form:
  606.  
  607.      %type <name> symbol ...
  608.  
  609.   e.g.:
  610.  
  611.      %type <Real> expr
  612.  
  613.   In a %type definition, you may also omit the nonterminals, i.e. you
  614.   may write:
  615.  
  616.      %type <name>
  617.  
  618.   This is useful when a given type is only used with type casts (see
  619.   Section `Grammar Rules and Actions'), and is not associated with a
  620.   specific nonterminal.
  621.  
  622. - Turbo Pascal declarations: You may also include arbitrary Turbo Pascal
  623.   code in the definitions section, enclosed in %{ %}. This code will be
  624.   inserted as global declarations into the output file, unchanged.
  625.  
  626.  
  627. Grammar Rules and Actions
  628. -------------------------
  629.  
  630. The second part of a TP Yacc grammar contains the grammar rules for the
  631. target language. Grammar rules have the format
  632.  
  633.    name : symbol ... ;
  634.  
  635. The left-hand side of a rule must be an identifier (which denotes a
  636. nonterminal symbol). The right-hand side may be an arbitrary (possibly
  637. empty) sequence of nonterminal and terminal symbols (including literals
  638. enclosed in single quotes). The terminating semicolon may also be omitted.
  639. Different rules for the same left-hand side symbols may be written using
  640. the | character to separate the different alternatives:
  641.  
  642.    name : symbol ...
  643.         | symbol ...
  644.         ...
  645.         ;
  646.  
  647. For instance, to specify a simple grammar for arithmetic expressions, you
  648. may write:
  649.  
  650. %left '+' '-'
  651. %left '*' '/'
  652. %token NUM
  653. %%
  654. expr : expr '+' expr
  655.      | expr '-' expr
  656.      | expr '*' expr
  657.      | expr '/' expr
  658.      | '(' expr ')'
  659.      | NUM
  660.      ;
  661.  
  662. (The %left definitions at the beginning of the grammar are needed to specify
  663. the precedence and associativity of the operator symbols. This will be
  664. discussed in more detail in Section `Ambigious Grammars'.)
  665.  
  666. Grammar rules may contain actions - Turbo Pascal statements enclosed in
  667. { } - to be executed as the corresponding rules are recognized. Furthermore,
  668. rules may return values, and access values returned by other rules. These
  669. "semantic" values are written as $$ (value of the left-hand side nonterminal)
  670. and $i (value of the ith right-hand side symbol). They are kept on a special
  671. value stack which is maintained automatically by the parser.
  672.  
  673. Values associated with terminal symbols must be set by the lexical analyzer
  674. (more about this in Section `Lexical Analysis'). Actions of the form $$ := $1
  675. can frequently be omitted, since it is the default action assumed by TP Yacc
  676. for any rule that does not have an explicit action.
  677.  
  678. By default, the semantic value type provided by Yacc is Integer. You can
  679. also put a declaration like
  680.  
  681.    %{
  682.    type YYSType = Real;
  683.    %}
  684.  
  685. into the definitions section of your Yacc grammar to change the default value
  686. type. However, if you have different value types, the preferred method is to
  687. use type definitions as discussed in Section `Definitions'. When such type
  688. definitions are given, TP Yacc handles all the necessary details of the
  689. YYSType definition and also provides a fair amount of type checking which
  690. makes it easier to find type errors in the grammar.
  691.  
  692. For instance, we may declare the symbols NUM and expr in the example above
  693. to be of type Real, and then use these values to evaluate an expression as
  694. it is parsed.
  695.  
  696. %left '+' '-'
  697. %left '*' '/'
  698. %token <Real> NUM
  699. %type  <Real> expr
  700. %%
  701. expr : expr '+' expr   { $$ := $1+$3; }
  702.      | expr '-' expr   { $$ := $1-$3; }
  703.      | expr '*' expr   { $$ := $1*$3; }
  704.      | expr '/' expr   { $$ := $1/$3; }
  705.      | '(' expr ')'    { $$ := $2;    }
  706.      | NUM
  707.      ;
  708.  
  709. (Note that we omitted the action of the last rule. The "copy action"
  710. $$ := $1 required by this rule is automatically added by TP Yacc.)
  711.  
  712. Actions may not only appear at the end, but also in the middle of a rule
  713. which is useful to perform some processing before a rule is fully parsed.
  714. Such actions inside a rule are treated as special nonterminals which are
  715. associated with an empty right-hand side. Thus, a rule like
  716.  
  717.    x : y { action; } z
  718.  
  719. will be treated as:
  720.  
  721.   x : y $act z
  722.   $act : { action; }
  723.  
  724. Actions inside a rule may also access values to the left of the action,
  725. and may return values by assigning to the $$ value. The value returned
  726. by such an action can then be accessed by other actions using the usual $i
  727. notation. E.g., we may write:
  728.  
  729.    x : y { $$ := 2*$1; } z { $$ := $2+$3; }
  730.  
  731. which has the effect of setting the value of x to
  732.  
  733.    2*(the value of y)+(the value of z).
  734.  
  735. Sometimes it is desirable to access values in enclosing rules. This can be
  736. done using the notation $i with i<=0. $0 refers to the first value "to the
  737. left" of the current rule, $-1 to the second, and so on. Note that in this
  738. case the referenced value depends on the actual contents of the parse stack,
  739. so you have to make sure that the requested values are always where you
  740. expect them.
  741.  
  742. There are some situations in which TP Yacc cannot easily determine the
  743. type of values (when a typed parser is used). This is true, in particular,
  744. for values in enclosing rules and for the $$ value in an action inside a
  745. rule. In such cases you may use a type cast to explicitly specify the type
  746. of a value. The format for such type casts is $<name>$ (for left-hand side
  747. values) and $<name>i (for right-hand side values) where name is a type
  748. identifier (which must occur in a %token, precedence or %type definition).
  749.  
  750.  
  751. Auxiliary Procedures
  752. --------------------
  753.  
  754. The third section of a TP Yacc program is optional. If it is present, it
  755. may contain any Turbo Pascal code (such as supporting routines or a main
  756. program) which is tacked on to the end of the output file.
  757.  
  758.  
  759. Lexical Analysis
  760. ----------------
  761.  
  762. For any TP Yacc-generated parser, the programmer must supply a lexical
  763. analyzer routine named yylex which performs the lexical analysis for
  764. the parser. This routine must be declared as
  765.  
  766.    function yylex : Integer;
  767.  
  768. The yylex routine may either be prepared by hand, or by using the lexical
  769. analyzer generator TP Lex (see Section `TP Lex').
  770.  
  771. The lexical analyzer must be included in your main program behind the
  772. parser subroutine (the yyparse code template includes a forward
  773. definition of the yylex routine such that the parser can access the
  774. lexical analyzer). For instance, you may put the lexical analyzer
  775. routine into the auxiliary procedures section of your TP Yacc grammar,
  776. either directly, or by using the the Turbo Pascal include directive
  777. ($I).
  778.  
  779. The parser repeatedly calls the yylex routine to tokenize the input
  780. stream and obtain the individual lexical items in the input. For any
  781. literal character, the yylex routine has to return the corresponding
  782. character code. For the other, symbolic, terminals of the input language,
  783. the lexical analyzer must return corresponding Integer codes. These are
  784. assigned automatically by TP Yacc in the order in which token definitions
  785. appear in the definitions section of the source grammar. The lexical
  786. analyzer can access these values through corresponding Integer constants
  787. which are declared by TP Yacc in the output file.
  788.  
  789. For instance, if
  790.  
  791.    %token NUM
  792.  
  793. is the first definition in the Yacc grammar, then TP Yacc will create
  794. a corresponding constant declaration
  795.  
  796.    const NUM = 257;
  797.  
  798. in the output file (TP Yacc automatically assigns symbolic token numbers
  799. starting at 257; 1 thru 255 are reserved for character literals, 0 denotes
  800. end-of-file, and 256 is reserved for the special error token which will be
  801. discussed in Section `Error Handling'). This definition may then be used,
  802. e.g., in a corresponding TP Lex program as follows:
  803.  
  804.    [0-9]+   return(NUM);
  805.  
  806. You can also explicitly assign token numbers in the grammar. For this
  807. purpose, the first occurrence of a token identifier in the definitions
  808. section may be followed by an unsigned integer. E.g. you may write:
  809.  
  810.    %token NUM 299
  811.  
  812. Besides the return value of yylex, the lexical analyzer routine may also
  813. return an additional semantic value for the recognized token. This value
  814. is assigned to a variable named "yylval" and may then be accessed in actions
  815. through the $i notation (see above, Section `Grammar Rules and Actions').
  816. The yylval variable is of type YYSType (the semantic value type, Integer
  817. by default); its declaration may be found in the YYPARSE.COD file.
  818.  
  819. For instance, to assign an Integer value to a NUM token in the above
  820. example, we may write:
  821.  
  822.    [0-9]+   begin
  823.               val(yytext, yylval, code);
  824.               return(NUM);
  825.             end;
  826.  
  827. This assigns yylval the value of the NUM token (using the Turbo Pascal
  828. standard procedure val).
  829.  
  830. If a parser uses tokens of different types (via a %token <name> definition),
  831. then the yylval variable will not be of type Integer, but instead of a
  832. corresponding variant record type which is capable of holding all the
  833. different value types declared in the TP Yacc grammar. In this case, the
  834. lexical analyzer must assign a semantic value to the corresponding record
  835. component which is named yy<name> (where <name> stands for the corresponding
  836. type identifier).
  837.  
  838. E.g., if token NUM is declared Real:
  839.  
  840.    %token <Real> NUM
  841.  
  842. then the value for token NUM must be assigned to yylval.yyReal.
  843.  
  844.  
  845. How The Parser Works
  846. --------------------
  847.  
  848. TP Yacc uses the LALR(1) technique developed by Donald E. Knuth and F.
  849. DeRemer to construct a simple, efficient, non-backtracking bottom-up
  850. parser for the source grammar. The LALR parsing technique is described
  851. in detail in Aho/Sethi/Ullman (1986). It is quite instructive to take a
  852. look at the parser description TP Yacc generates from a small sample
  853. grammar, to get an idea of how the LALR parsing algorithm works. We
  854. consider the following simplified version of the arithmetic expression
  855. grammar:
  856.  
  857. %token NUM
  858. %left '+'
  859. %left '*'
  860. %%
  861. expr : expr '+' expr
  862.      | expr '*' expr
  863.      | '(' expr ')'
  864.      | NUM
  865.      ;
  866.  
  867. When run with the /v option on the above grammar, TP Yacc generates the
  868. parser description listed below.
  869.  
  870. state 0:
  871.  
  872.     $accept : _ expr $end
  873.  
  874.     '('    shift 2
  875.     NUM    shift 3
  876.     .    error
  877.  
  878.     expr    goto 1
  879.  
  880. state 1:
  881.  
  882.     $accept : expr _ $end
  883.     expr : expr _ '+' expr
  884.     expr : expr _ '*' expr
  885.  
  886.     $end    accept
  887.     '*'    shift 4
  888.     '+'    shift 5
  889.     .    error
  890.  
  891. state 2:
  892.  
  893.     expr : '(' _ expr ')'
  894.  
  895.     '('    shift 2
  896.     NUM    shift 3
  897.     .    error
  898.  
  899.     expr    goto 6
  900.  
  901. state 3:
  902.  
  903.     expr : NUM _    (4)
  904.  
  905.     .    reduce 4
  906.  
  907. state 4:
  908.  
  909.     expr : expr '*' _ expr
  910.  
  911.     '('    shift 2
  912.     NUM    shift 3
  913.     .    error
  914.  
  915.     expr    goto 7
  916.  
  917. state 5:
  918.  
  919.     expr : expr '+' _ expr
  920.  
  921.     '('    shift 2
  922.     NUM    shift 3
  923.     .    error
  924.  
  925.     expr    goto 8
  926.  
  927. state 6:
  928.  
  929.     expr : '(' expr _ ')'
  930.     expr : expr _ '+' expr
  931.     expr : expr _ '*' expr
  932.  
  933.     ')'    shift 9
  934.     '*'    shift 4
  935.     '+'    shift 5
  936.     .    error
  937.  
  938. state 7:
  939.  
  940.     expr : expr '*' expr _    (2)
  941.     expr : expr _ '+' expr
  942.     expr : expr _ '*' expr
  943.  
  944.     .    reduce 2
  945.  
  946. state 8:
  947.  
  948.     expr : expr '+' expr _    (1)
  949.     expr : expr _ '+' expr
  950.     expr : expr _ '*' expr
  951.  
  952.     '*'    shift 4
  953.     $end    reduce 1
  954.     ')'    reduce 1
  955.     '+'    reduce 1
  956.     .    error
  957.  
  958. state 9:
  959.  
  960.     expr : '(' expr ')' _    (3)
  961.  
  962.     .    reduce 3
  963.  
  964.  
  965. Each state of the parser corresponds to a certain prefix of the input
  966. which has already been seen. The parser description lists the grammar
  967. rules wich are parsed in each state, and indicates the portion of each
  968. rule which has already been parsed by an underscore. In state 0, the
  969. start state of the parser, the parsed rule is
  970.  
  971.     $accept : expr $end
  972.  
  973. This is not an actual grammar rule, but a starting rule automatically
  974. added by TP Yacc. In general, it has the format
  975.  
  976.     $accept : X $end
  977.  
  978. where X is the start nonterminal of the grammar, and $end is a pseudo
  979. token denoting end-of-input (the $end symbol is used by the parser to
  980. determine when it has successfully parsed the input).
  981.  
  982. The description of the start rule in state 0,
  983.  
  984.     $accept : _ expr $end
  985.  
  986. with the underscore positioned before the expr symbol, indicates that
  987. we are at the beginning of the parse and are ready to parse an expression
  988. (nonterminal expr).
  989.  
  990. The parser maintains a stack to keep track of states visited during the
  991. parse. There are two basic kinds of actions in each state: "shift", which
  992. reads an input symbol and pushes the corresponding next state on top of
  993. the stack, and "reduce" which pops a number of states from the stack
  994. (corresponding to the number of right-hand side symbols of the rule used
  995. in the reduction) and consults the "goto" entries of the uncovered state
  996. to find the transition corresponding to the left-hand side symbol of the
  997. reduced rule.
  998.  
  999. In each step of the parse, the parser is in a given state (the state on
  1000. top of its stack) and may consult the current "lookahead symbol", the
  1001. next symbol in the input, to determine the parse action - shift or reduce -
  1002. to perform. The parser terminates as soon as it reaches state 1 and reads
  1003. in the endmarker, indicated by the "accept" action on $end in state 1.
  1004.  
  1005. Sometimes the parser may also carry out an action without inspecting the
  1006. current lookahead token. This is the case, e.g., in state 3 where the
  1007. only action is reduction by rule 4:
  1008.  
  1009.     .    reduce 4
  1010.  
  1011. The default action in a state can also be "error" indicating that any
  1012. other input represents a syntax error. (In case of such an error the
  1013. parser will start syntactic error recovery, as described in Section
  1014. `Error Handling'.)
  1015.  
  1016. Now let us see how the parser responds to a given input. We consider the
  1017. input string 2+5*3 which is presented to the parser as the token sequence:
  1018.  
  1019.    NUM + NUM * NUM
  1020.  
  1021. The following table traces the corresponding actions of the parser. We also
  1022. show the current state in each move, and the remaining states on the stack.
  1023.  
  1024. State  Stack         Lookahead  Action
  1025. -----  ------------  ---------  --------------------------------------------
  1026.  
  1027. 0                    NUM        shift state 3
  1028.  
  1029. 3      0                        reduce rule 4 (pop 1 state, uncovering state
  1030.                                 0, then goto state 1 on symbol expr)
  1031.  
  1032. 1      0             +          shift state 5
  1033.  
  1034. 5      1 0           NUM        shift state 3
  1035.  
  1036. 3      5 1 0                    reduce rule 4 (pop 1 state, uncovering state
  1037.                                 5, then goto state 8 on symbol expr)
  1038.  
  1039. 8      5 1 0         *          shift 4
  1040.  
  1041. 4      8 5 1 0       NUM        shift 3
  1042.  
  1043. 3      4 8 5 1 0                reduce rule 4 (pop 1 state, uncovering state
  1044.                                 4, then goto state 7 on symbol expr)
  1045.  
  1046. 7      4 8 5 1 0                reduce rule 2 (pop 3 states, uncovering state
  1047.                                 5, then goto state 8 on symbol expr)
  1048.  
  1049. 8      5 1 0         $end       reduce rule 1 (pop 3 states, uncovering state
  1050.                                 0, then goto state 1 on symbol expr)
  1051.  
  1052. 1      0             $end       accept
  1053.  
  1054. It is also instructive to see how the parser responds to illegal inputs.
  1055. E.g., you may try to figure out what the parser does when confronted with:
  1056.  
  1057.    NUM + )
  1058.  
  1059. or:
  1060.  
  1061.    ( NUM * NUM
  1062.  
  1063. You will find that the parser, sooner or later, will always run into an
  1064. error action when confronted with errorneous inputs. An LALR parser will
  1065. never shift an invalid symbol and thus will always find syntax errors as
  1066. soon as it is possible during a left-to-right scan of the input.
  1067.  
  1068. TP Yacc provides a debugging option (/d) that may be used to trace the
  1069. actions performed by the parser. When a grammar is compiled with the
  1070. /d option, the generated parser will print out the actions as it parses
  1071. its input.
  1072.  
  1073.  
  1074. Ambigious Grammars
  1075. ------------------
  1076.  
  1077. There are situations in which TP Yacc will not produce a valid parser for
  1078. a given input language. LALR(1) parsers are restricted to one-symbol
  1079. lookahead on which they have to base their parsing decisions. If a
  1080. grammar is ambigious, or cannot be parsed unambigiously using one-symbol
  1081. lookahead, TP Yacc will generate parsing conflicts when constructing the
  1082. parse table. There are two types of such conflicts: shift/reduce conflicts
  1083. (when there is both a shift and a reduce action for a given input symbol
  1084. in a given state), and reduce/reduce conflicts (if there is more than
  1085. one reduce action for a given input symbol in a given state). Note that
  1086. there never will be a shift/shift conflict.
  1087.  
  1088. When a grammar generates parsing conflicts, TP Yacc prints out the number
  1089. of shift/reduce and reduce/reduce conflicts it encountered when constructing
  1090. the parse table. However, TP Yacc will still generate the output code for the
  1091. parser. To resolve parsing conflicts, TP Yacc uses the following built-in
  1092. disambiguating rules:
  1093.  
  1094. - in a shift/reduce conflict, TP Yacc chooses the shift action.
  1095.  
  1096. - in a reduce/reduce conflict, TP Yacc chooses reduction of the first
  1097.   grammar rule.
  1098.  
  1099. The shift/reduce disambiguating rule correctly resolves a type of
  1100. ambiguity known as the "dangling-else ambiguity" which arises in the
  1101. syntax of conditional statements of many programming languages (as in
  1102. Pascal):
  1103.  
  1104. %token IF THEN ELSE
  1105. %%
  1106. stmt : IF expr THEN stmt
  1107.      | IF expr THEN stmt ELSE stmt
  1108.      ;
  1109.  
  1110. This grammar is ambigious, because a nested construct like
  1111.  
  1112.    IF expr-1 THEN IF expr-2 THEN stmt-1 ELSE stmt-2
  1113.  
  1114. can be parsed two ways, either as:
  1115.  
  1116.    IF expr-1 THEN ( IF expr-2 THEN stmt-1 ELSE stmt-2 )
  1117.  
  1118. or as:
  1119.  
  1120.    IF expr-1 THEN ( IF expr-2 THEN stmt-1 ) ELSE stmt-2
  1121.  
  1122. The first interpretation makes an ELSE belong to the last unmatched
  1123. IF which also is the interpretation chosen in most programming languages.
  1124. This is also the way that a TP Yacc-generated parser will parse the construct
  1125. since the shift/reduce disambiguating rule has the effect of neglecting the
  1126. reduction of IF expr-2 THEN stmt-1; instead, the parser will shift the ELSE
  1127. symbol which eventually leads to the reduction of IF expr-2 THEN stmt-1 ELSE
  1128. stmt-2.
  1129.  
  1130. The reduce/reduce disambiguating rule is used to resolve conflicts that
  1131. arise when there is more than one grammar rule matching a given construct.
  1132. Such ambiguities are often caused by "special case constructs" which may be
  1133. given priority by simply listing the more specific rules ahead of the more
  1134. general ones.
  1135.  
  1136. For instance, the following is an excerpt from the grammar describing the
  1137. input language of the UNIX equation formatter EQN:
  1138.  
  1139. %right SUB SUP
  1140. %%
  1141. expr : expr SUB expr SUP expr
  1142.      | expr SUB expr
  1143.      | expr SUP expr
  1144.      ;
  1145.  
  1146. Here, the SUB and SUP operator symbols denote sub- and superscript,
  1147. respectively. The rationale behind this example is that an expression
  1148. involving both sub- and superscript is often set differently from a
  1149. superscripted subscripted expression. This special case is therefore
  1150. caught by the first rule in the above example which causes a reduce/reduce
  1151. conflict with rule 3 in expressions like expr-1 SUB expr-2 SUP expr-3.
  1152. The conflict is resolved in favour of the first rule.
  1153.  
  1154. In both cases discussed above, the ambiguities could also be eliminated
  1155. by rewriting the grammar accordingly (although this yields more complicated
  1156. and less readable grammars). This may not always be the case. Often
  1157. ambiguities are also caused by design errors in the grammar. Hence, if
  1158. TP Yacc reports any parsing conflicts when constructing the parser, you
  1159. should use the /v option to generate the parser description (.LST file)
  1160. and check whether TP Yacc resolved the conflicts correctly.
  1161.  
  1162. There is one type of syntactic constructs for which one often deliberately
  1163. uses an ambigious grammar as a more concise representation for a language
  1164. that could also be specified unambigiously: the syntax of expressions.
  1165. For instance, the following is an unambigious grammar for simple arithmetic
  1166. expressions:
  1167.  
  1168. %token NUM
  1169.  
  1170. %%
  1171.  
  1172. expr    : term
  1173.     | expr '+' term
  1174.         ;
  1175.  
  1176. term    : factor
  1177.     | term '*' factor
  1178.         ;
  1179.  
  1180. factor    : '(' expr ')'
  1181.     | NUM
  1182.         ;
  1183.  
  1184. You may check yourself that this grammar gives * a higher precedence than
  1185. + and makes both operators left-associative. The same effect can be achieved
  1186. with the following ambigious grammar using precedence definitions:
  1187.  
  1188. %token NUM
  1189. %left '+'
  1190. %left '*'
  1191. %%
  1192. expr : expr '+' expr
  1193.      | expr '*' expr
  1194.      | '(' expr ')'
  1195.      | NUM
  1196.      ;
  1197.  
  1198. Without the precedence definitions, this is an ambigious grammar causing
  1199. a number of shift/reduce conflicts. The precedence definitions are used
  1200. to correctly resolve these conflicts (conflicts resolved using precedence
  1201. will not be reported by TP Yacc).
  1202.  
  1203. Each precedence definition introduces a new precedence level (lowest
  1204. precedence first) and specifies whether the corresponding operators
  1205. should be left-, right- or nonassociative (nonassociative operators
  1206. cannot be combined at all; example: relational operators in Pascal).
  1207.  
  1208. TP Yacc uses precedence information to resolve shift/reduce conflicts as
  1209. follows. Precedences are associated with each terminal occuring in a
  1210. precedence definition. Furthermore, each grammar rule is given the
  1211. precedence of its rightmost terminal (this default choice can be
  1212. overwritten using a %prec tag; see below). To resolve a shift/reduce
  1213. conflict using precedence, both the symbol and the rule involved must
  1214. have been assigned precedences. TP Yacc then chooses the parse action
  1215. as follows:
  1216.  
  1217. - If the symbol has higher precedence than the rule: shift.
  1218.  
  1219. - If the rule has higher precedence than the symbol: reduce.
  1220.  
  1221. - If symbol and rule have the same precedence, the associativity of the
  1222.   symbol determines the parse action: if the symbol is left-associative:
  1223.   reduce; if the symbol is right-associative: shift; if the symbol is
  1224.   non-associative: error.
  1225.  
  1226. To give you an idea of how this works, let us consider our ambigious
  1227. arithmetic expression grammar (without precedences):
  1228.  
  1229. %token NUM
  1230. %%
  1231. expr : expr '+' expr
  1232.      | expr '*' expr
  1233.      | '(' expr ')'
  1234.      | NUM
  1235.      ;
  1236.  
  1237. This grammar generates four shift/reduce conflicts. The description
  1238. of state 8 reads as follows:
  1239.  
  1240. state 8:
  1241.  
  1242.     *** conflicts:
  1243.  
  1244.     shift 4, reduce 1 on '*'
  1245.     shift 5, reduce 1 on '+'
  1246.  
  1247.     expr : expr '+' expr _    (1)
  1248.     expr : expr _ '+' expr
  1249.     expr : expr _ '*' expr
  1250.  
  1251.     '*'    shift 4
  1252.     '+'    shift 5
  1253.     $end    reduce 1
  1254.     ')'    reduce 1
  1255.     .    error
  1256.  
  1257. In this state, we have successfully parsed a + expression (rule 1). When
  1258. the next symbol is + or *, we have the choice between the reduction and
  1259. shifting the symbol. Using the default shift/reduce disambiguating rule,
  1260. TP Yacc has resolved these conflicts in favour of shift.
  1261.  
  1262. Now let us assume the above precedence definition:
  1263.  
  1264.    %left '+'
  1265.    %left '*'
  1266.  
  1267. which gives * higher precedence than + and makes both operators left-
  1268. associative. The rightmost terminal in rule 1 is +. Hence, given these
  1269. precedence definitions, the first conflict will be resolved in favour
  1270. of shift (* has higher precedence than +), while the second one is resolved
  1271. in favour of reduce (+ is left-associative).
  1272.  
  1273. Similar conflicts arise in state 7:
  1274.  
  1275. state 7:
  1276.  
  1277.     *** conflicts:
  1278.  
  1279.     shift 4, reduce 2 on '*'
  1280.     shift 5, reduce 2 on '+'
  1281.  
  1282.     expr : expr '*' expr _    (2)
  1283.     expr : expr _ '+' expr
  1284.     expr : expr _ '*' expr
  1285.  
  1286.     '*'    shift 4
  1287.     '+'    shift 5
  1288.     $end    reduce 2
  1289.     ')'    reduce 2
  1290.     .    error
  1291.  
  1292. Here, we have successfully parsed a * expression which may be followed
  1293. by another + or * operator. Since * is left-associative and has higher
  1294. precedence than +, both conflicts will be resolved in favour of reduce.
  1295.  
  1296. Of course, you can also have different operators on the same precedence
  1297. level. For instance, consider the following extended version of the
  1298. arithmetic expression grammar:
  1299.  
  1300. %token NUM
  1301. %left '+' '-'
  1302. %left '*' '/'
  1303. %%
  1304. expr    : expr '+' expr
  1305.     | expr '-' expr
  1306.         | expr '*' expr
  1307.         | expr '/' expr
  1308.         | '(' expr ')'
  1309.         | NUM
  1310.         ;
  1311.  
  1312. This puts all "addition" operators on the first and all "multiplication"
  1313. operators on the second precedence level. All operators are left-associative;
  1314. for instance, 5+3-2 will be parsed as (5+3)-2.
  1315.  
  1316. By default, TP Yacc assigns each rule the precedence of its rightmost
  1317. terminal. This is a sensible decision in most cases. Occasionally, it
  1318. may be necessary to overwrite this default choice and explicitly assign
  1319. a precedence to a rule. This can be done by putting a precedence tag
  1320. of the form
  1321.  
  1322.    %prec symbol
  1323.  
  1324. at the end of the corresponding rule which gives the rule the precedence
  1325. of the specified symbol. For instance, to extend the expression grammar
  1326. with a unary minus operator, giving it highest precedence, you may write:
  1327.  
  1328. %token NUM
  1329. %left '+' '-'
  1330. %left '*' '/'
  1331. %right UMINUS
  1332. %%
  1333. expr    : expr '+' expr
  1334.     | expr '-' expr
  1335.         | expr '*' expr
  1336.         | expr '/' expr
  1337.         | '-' expr      %prec UMINUS
  1338.         | '(' expr ')'
  1339.         | NUM
  1340.         ;
  1341.  
  1342. Note the use of the UMINUS token which is not an actual input symbol but
  1343. whose sole purpose it is to give unary minus its proper precedence. If
  1344. we omitted the precedence tag, both unary and binary minus would have the
  1345. same precedence because they are represented by the same input symbol.
  1346.  
  1347.  
  1348. Error Handling
  1349. --------------
  1350.  
  1351. Syntactic error handling is a difficult area in the design of user-friendly
  1352. parsers. Usually, you will not like to have the parser give up upon the
  1353. first occurrence of an errorneous input symbol. Instead, the parser should
  1354. recover from a syntax error, that is, it should try to find a place in the
  1355. input where it can resume the parse.
  1356.  
  1357. TP Yacc provides a general mechanism to implement parsers with error
  1358. recovery. A special predefined "error" token may be used in grammar rules
  1359. to indicate positions where syntax errors might occur. When the parser runs
  1360. into an error action (i.e., reads an errorneous input symbol) it prints out
  1361. an error message and starts error recovery by popping its stack until it
  1362. uncovers a state in which there is a shift action on the error token. If
  1363. there is no such state, the parser terminates with return value 1, indicating
  1364. an unrecoverable syntax error. If there is such a state, the parser takes the
  1365. shift on the error token (pretending it has seen an imaginary error token in
  1366. the input), and resumes parsing in a special "error mode."
  1367.  
  1368. While in error mode, the parser quietly skips symbols until it can again
  1369. perform a legal shift action. To prevent a cascade of error messages, the
  1370. parser returns to its normal mode of operation only after it has seen
  1371. and shifted three legal input symbols. Any additional error found after
  1372. the first shifted symbol restarts error recovery, but no error message
  1373. is printed. The TP Yacc library routine yyerrok may be used to reset the
  1374. parser to its normal mode of operation explicitly.
  1375.  
  1376. For a simple example, consider the rule
  1377.  
  1378. stmt    : error ';' { yyerrok; }
  1379.  
  1380. and assume a syntax error occurs while a statement (nonterminal stmt) is
  1381. parsed. The parser prints an error message, then pops its stack until it
  1382. can shift the token error of the error rule. Proceeding in error mode, it
  1383. will skip symbols until it finds a semicolon, then reduces by the error
  1384. rule. The call to yyerrok tells the parser that we have recovered from
  1385. the error and that it should proceed with the normal parse. This kind of
  1386. "panic mode" error recovery scheme works well when statements are always
  1387. terminated with a semicolon. The parser simply skips the "bad" statement
  1388. and then resumes the parse.
  1389.  
  1390. Implementing a good error recovery scheme can be a difficult task; see
  1391. Aho/Sethi/Ullman (1986) for a more comprehensive treatment of this topic.
  1392. Schreiner and Friedman have developed a systematic technique to implement
  1393. error recovery with Yacc which I found quite useful (I used it myself
  1394. to implement error recovery in the TP Yacc parser); see Schreiner/Friedman
  1395. (1985).
  1396.  
  1397.  
  1398. Yacc Library
  1399. ------------
  1400.  
  1401. The TP Yacc library (YaccLib) unit provides some global declarations used
  1402. by the parser routine yyparse, and some variables and utility routines
  1403. which may be used to control the actions of the parser and to implement
  1404. error recovery. See the file YACCLIB.PAS for a description of these
  1405. variables and routines.
  1406.  
  1407. You can also modify the Yacc library unit (and/or the code template in the
  1408. YYPARSE.COD file) to customize TP Yacc to your target applications.
  1409.  
  1410.  
  1411. Other Features
  1412. --------------
  1413.  
  1414. TP Yacc supports all additional language elements entitled as "Old Features
  1415. Supported But not Encouraged" in the UNIX manual, which are provided for
  1416. backward compatibility with older versions of (UNIX) Yacc:
  1417.  
  1418. - literals delimited by double quotes.
  1419.  
  1420. - multiple-character literals. Note that these are not treated as character
  1421.   sequences but represent single tokens which are given a symbolic integer
  1422.   code just like any other token identifier. However, they will not be
  1423.   declared in the output file, so you have to make sure yourself that
  1424.   the lexical analyzer returns the correct codes for these symbols. E.g.,
  1425.   you might explicitly assign token numbers by using a definition like
  1426.  
  1427.      %token ':=' 257
  1428.  
  1429.   at the beginning of the Yacc grammar.
  1430.  
  1431. - \ may be used instead of %, i.e. \\ means %%, \left is the same as %left,
  1432.   etc.
  1433.  
  1434. - other synonyms:
  1435.   %<             for %left
  1436.   %>             for %right
  1437.   %binary or %2  for %nonassoc
  1438.   %term or %0    for %token
  1439.   %=             for %prec
  1440.  
  1441. - actions may also be written as = { ... } or = single-statement;
  1442.  
  1443. - Turbo Pascal declarations (%{ ... %}) may be put at the beginning of the
  1444.   rules section. They will be treated as local declarations of the actions
  1445.   routine.
  1446.  
  1447.  
  1448. Implementation Restrictions
  1449. ---------------------------
  1450.  
  1451. As with TP Lex, internal table sizes and the main memory available limit the
  1452. complexity of source grammars that TP Yacc can handle. There is currently no
  1453. possibility to change internal table sizes (apart from modifying the sources
  1454. of TP Yacc itself) or to make use of extended memory. However, the maximum
  1455. table sizes provided by TP Yacc are large enough to handle quite complex
  1456. grammars (such as the Pascal grammar in the TP Yacc distribution). The
  1457. current limits are 600 s (states), 2400 i (LR0 kernel items), 2400 t (shift
  1458. and goto transitions) and 1200 r (reductions).
  1459.  
  1460. The default stack size of the generated parsers is yymaxdepth = 1024, as
  1461. declared in the TP Yacc library unit. This should be sufficient for any
  1462. average application, but you can change the stack size by including a
  1463. corresponding declaration in the definitions part of the Yacc grammar
  1464. (or change the value in the YaccLib unit). Note that right-recursive
  1465. grammar rules may increase stack space requirements, so it is a good
  1466. idea to use left-recursive rules wherever possible.
  1467.  
  1468.  
  1469. Differences from UNIX Yacc
  1470. --------------------------
  1471.  
  1472. Major differences between TP Yacc and UNIX Yacc are listed below.
  1473.  
  1474. - TP Yacc produces output code for Turbo Pascal, rather than for C.
  1475.  
  1476. - TP Yacc does not support %union definitions. Instead, a value type is
  1477.   declared by specifying the type identifier itself as the tag of a %token
  1478.   or %type definition. TP Yacc will automatically generate an appropriate
  1479.   variant record type (YYSType) which is capable of holding values of any
  1480.   of the types used in %token and %type.
  1481.  
  1482.   Type checking is very strict. If you use type definitions, then
  1483.   any symbol referred to in an action must have a type introduced
  1484.   in a type definition. Either the symbol must have been assigned a
  1485.   type in the definitions section, or the $<type-identifier> notation
  1486.   must be used. The syntax of the %type definition has been changed
  1487.   slightly to allow definitions of the form
  1488.      %type <type-identifier>
  1489.   (omitting the nonterminals) which may be used to declare types which
  1490.   are not assigned to any grammar symbol, but are used with the
  1491.   $<...> construct.
  1492.  
  1493. - The parse tables constructed by this Yacc version are slightly greater
  1494.   than those constructed by UNIX Yacc, since a reduce action will only be
  1495.   chosen as the default action if it is the only action in the state.
  1496.   In difference, UNIX Yacc chooses a reduce action as the default action
  1497.   whenever it is the only reduce action of the state (even if there are
  1498.   other shift actions).
  1499.  
  1500.   This solves a bug in UNIX Yacc that makes the generated parser start
  1501.   error recovery too late with certain types of error productions (see
  1502.   also Schreiner/Friedman, "Introduction to compiler construction with
  1503.   UNIX," 1985). Also, errors will be caught sooner in most cases where
  1504.   UNIX Yacc would carry out an additional (default) reduction before
  1505.   detecting the error.
  1506.  
  1507. - Library routines are named differently from the UNIX version (e.g.,
  1508.   the `yyerrlab' routine takes the place of the `YYERROR' macro of UNIX
  1509.   Yacc), and, of course, all macros of UNIX Yacc (YYERROR, YYACCEPT, etc.)
  1510.   had to be implemented as procedures.
  1511.  
  1512.